package main

import "fmt"

var _ = `
438. 找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 
异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
 示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
 

提示:
1 <= s.length, p.length <= 3 * 104
s 和 p 仅包含小写字母
`

func findAnagrams(s string, p string) []int {
	res := make([]int, 0)
	num := len(p)

	// m存储当前需要判断的字符串
	m := [26]int{}

	pm := [26]int{}
	for _, v := range p {
		pm[v-'a']++
	}

	if len(s) < len(p) {
		return res
	}

	// 初始化
	for k := 0; k < num; k++ {
		m[rune(s[k])-rune('a')]++
	}

	for i, j := 0, num-1; i <= j && j <= len(s); {
		ok := pm == m
		if ok {
			res = append(res, i)
		}
		// 移动窗口
		m[rune(s[i])-rune('a')]--
		i++
		j++
		if j >= len(s) {
			break
		}
		m[rune(s[j])-rune('a')]++
	}

	return res
}

func main() {
	s :=
		"aaaaaaaaaa"

	p :=
		"aaaaaaaaaaaaa"

	fmt.Println(findAnagrams(s, p))
}
